Search results for "Formal language"
showing 10 items of 357 documents
FO^2 with one transitive relation is decidable
2013
We show that the satisfiability problem for the two-variable first-order logic, FO^2, over transitive structures when only one relation is required to be transitive, is decidable. The result is optimal, as FO^2 over structures with two transitive relations, or with one transitive and one equivalence relation, are known to be undecidable, so in fact, our result completes the classification of FO^2-logics over transitive structures with respect to decidability. We show that the satisfiability problem is in 2-NExpTime. Decidability of the finite satisfiability problem remains open.
Alignment-free sequence comparison using absent words
2018
Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as $q$-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an {\em absent word} of some sequence if it does not oc…
DNA combinatorial messages and Epigenomics: The case of chromatin organization and nucleosome occupancy in eukaryotic genomes
2019
Abstract Epigenomics is the study of modifications on the genetic material of a cell that do not depend on changes in the DNA sequence, since those latter involve specific proteins around which DNA wraps. The end result is that Epigenomic changes have a fundamental role in the proper working of each cell in Eukaryotic organisms. A particularly important part of Epigenomics concentrates on the study of chromatin, that is, a fiber composed of a DNA-protein complex and very characterizing of Eukaryotes. Understanding how chromatin is assembled and how it changes is fundamental for Biology. In more than thirty years of research in this area, Mathematics and Theoretical Computer Science have gai…
Sense Equivalence in plWordNet to Princeton WordNet Mapping
2019
Abstract Though the interest in use of wordnets for lexicography is (gradually) growing, no research has been conducted so far on equivalence between lexical units (or senses) in inter-linked wordnets. In this paper, we present and validate a procedure of sense-linking between plWordNet and Princeton WordNet. The proposed procedure employs a continuum of three equivalence types: strong, regular and weak, distinguished by a custom-designed set of formal, semantic and translational features. To validate the procedure, three independent samples of 120 sense pairs were manually analysed with respect to the features. The results show that synsets from the two wordnets linked by interlingual syno…
Who is looking at me? The cone of gaze widens in social phobia
2011
Gaze direction is an important cue that regulates social interactions and facilitates joint attention. Although humans are very accurate in determining gaze directions in general, they have a surprisingly liberal criterion for the presence of mutual gaze. Using an established psychophysical task that required observers to adjust the eyes of a virtual head to the margins of the area of mutual gaze, we examined whether the resulting cone of gaze is altered in people with social phobia. It turned out that during presence of a second virtual person, the gaze cone's width was specifically enlarged in patients with social phobia as compared to healthy controls. The size of this effect was correla…
Brain lateralization of metrical accenting in musicians.
2009
The perception of meter, or the alternation of strong and weak beats, was assessed in musically trained listeners through magnetoencephalography. Metrical accents were examined with no temporal disruption of the serial grouping of tones. Results showed an effect of metrical processing among identical standard tones in the left hemisphere, with larger responses on strong than on weak beats. Moreover, processing of occasional increases in intensity (phenomenal accents) varied as a function of metrical position in the left hemisphere, but not in the right. Our findings support the view of a relatively early, left-hemispheric effect of metrical processing in musicians.
TWO-DIMENSIONAL FINITE STATE RECOGNIZABILITY
1996
The purpose of this paper is to investigate about a new notion of finite state recognizability for two-dimensional (picture) languages. This notion takes as starting point the characterization of one-dimensional recognizable languages in terms of local languages and projections. Such notion can be extended in a natural way to the two-dimensional case. We first introduce a notion of local picture language and then we define,a recognizable picture language as a projection of a local picture language. The family of recognizable picture languages is denoted by REC. We study some combinatorial and language-theoretic properties of family REC. In particular we prove some closure properties with re…
Inductive synthesis of dot expressions
2005
We consider the problem of the synthesis of algorithms by sample computations. We introduce a formal language, namely, the so-called dot expressions, which is based on a formalization of the intuitive notion of ellipsis (‘...’). Whilst formally the dot expressions are simply a language describing sets of words, on the other hand, it can be considered as a programming language supporting quite a wide class of programs. Equivalence and asymptotical equivalence of dot expressions are defined and proved to be decidable. A formal example of a dot expression is defined in the way that, actually, it represents a sample computation of the program presented by the given dot expression. A system of s…
Multi-letter reversible and quantum finite automata
2007
The regular language (a+b)*a (the words in alphabet {a, b} having a as the last letter) is at the moment a classical example of a language not recognizable by a one-way quantum finite automaton (QFA). Up to now, there have been introduced many different models of QFAs, with increasing capabilities, but none of them can cope with this language. We introduce a new, quite simple modification of the QFA model (actually even a deterministic reversible FA model) which is able to recognize this language. We also completely characterise the set of languages recognizable by the new model FAs, by finding a "forbidden construction" whose presence or absence in the minimal deterministic (not necessaril…
Automatic calculation of massive two-loop self-energies with XLOOPS
1997
Abstract Within the program package XLOOPS it is possible to calculate self-energies up to the two-loop level for arbitrary massive particles. The program package — written in MAPLE (Char et al., Maple V Language Reference Manual (Springer, 1991); Char et al., Maple V Library Reference Manual (Springer, 1991)) — is designed to deal with the full tensor structure of the occurring integrals. This means that applications are not restricted to those cases where the reduction to scalars via equivalence theorem is allowed. The algorithms handle two-loop integrals analytically if this is possible. For those topologies where no analytic result for the general mass case is available, the diagrams ar…